package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/subsets-ii/'>子集 II(Subsets II)</a>
 * <p>给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。【数组的 子集 是从数组中选择一些元素（可能为空）。】</p>
 * <p>解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,2,2]
 *      输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 *
 * 示例 2：
 *      输入：nums = [0]
 *      输出：[[],[0]]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= nums.length <= 10</li>
 *         <li>-10 <= nums[i] <= 10</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/14 10:41
 */
public class LC0090Subsets_II_M {
    static class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> resList = new ArrayList<>();
            backtracking1(nums, 0, new boolean[nums.length], new ArrayList<>(), resList);
            //backtracking2(nums, 0, new ArrayList<>(), resList);
            //backtracking3(nums, 0, false, new ArrayList<>(), resList);
            return resList;
        }

        private void backtracking1(int[] nums, int startIdx, boolean[] used, List<Integer> path, List<List<Integer>> resList) {
            resList.add(new ArrayList<>(path));
            for (int currIdx = startIdx; currIdx < nums.length; currIdx++) {
                // 去重：如果当前值等于前一个值，并且前一个值没选，则当前数字值也不能选
                if (currIdx > startIdx && nums[currIdx] == nums[currIdx - 1] && !used[currIdx - 1]) {
                    continue;
                }
                // 处理
                used[currIdx] = true;
                path.add(nums[currIdx]);
                // 递归
                backtracking1(nums, currIdx + 1, used, path, resList);
                // 回溯
                used[currIdx] = false;
                path.remove(path.size() - 1);
            }
        }

        private void backtracking2(int[] nums, int currIdx, List<Integer> path, List<List<Integer>> resList) {
            if (currIdx == nums.length) {
                resList.add(new ArrayList<>(path));
                return;
            }
            // 1.选择当前数
            path.add(nums[currIdx]);    // 处理
            backtracking2(nums, currIdx + 1, path, resList);      // 递归
            path.remove(path.size() - 1);     // 回溯

            // 2.不选择当前数。后续与当前数相等的都需要跳过
            while (currIdx + 1 < nums.length && nums[currIdx] == nums[currIdx + 1]) {
                ++currIdx;
            }
            backtracking2(nums, currIdx + 1, path, resList);      // 递归
        }

        private void backtracking3(int[] nums, int currIdx, boolean ifChoosePre, List<Integer> path, List<List<Integer>> resList) {
            if (currIdx == nums.length) {
                resList.add(new ArrayList<>(path));
                return;
            }
            // 1.不选择当前数
            backtracking3(nums, currIdx + 1, false, path, resList); // 递归

            // 去重：如果当前值等于前一个值，并且前一个值没选，则当前数字值也不能选
            if (!ifChoosePre && currIdx > 0 && nums[currIdx] == nums[currIdx - 1]) {
                return;
            }

            // 2.选择当前数
            path.add(nums[currIdx]);    // 处理
            backtracking3(nums, currIdx + 1, true, path, resList);  // 递归
            path.remove(path.size() - 1);     // 回溯
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListListInteger(solution.subsetsWithDup(new int[]{1, 2, 2}));
        Printer.printListListInteger(solution.subsetsWithDup(new int[]{0}));
    }
}
